//
// This file is part of cpp-lib, a library of C++ functions and classes.
// Cpp-lib is copyright (C) 2004 and onwards, The CPL Interest Group.
// 
// This library is free software; you can redistribute it and/or modify it
// under the terms of the GNU Lesser General Public License as published by
// the Free Software Foundation; either version 2.1 of the License, or (at
// your option) any later version.
// 
// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser
// General Public License for more details.
// 
// You should have received a copy of the GNU Lesser General Public License
// along with this library (see the file COPYING); if not, write to the
// Free Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
// 02111-1307  USA
//
// $Id$
//


#ifndef CPP_LIB_UTIL_H
#define CPP_LIB_UTIL_H

#include <vector>
#include <string>
#include <fstream>
#include <sstream>
#include <memory>
#include <limits>

#include <cstdlib>
#include <cmath>
#include <cassert>

/// Always assert that \a expr is true.

/// This works like the standard assert() macro, except that it can't be
/// switched off by \c -DNDEBUG.

#define always_assert( expr )                                           \
  (                                                                     \
    ( expr )      ?                                                     \
    ( void( 0 ) ) :                                                     \
    cpl::util::assertion( false , #expr , __FILE__ , __LINE__ )     \
  )


/// Debug output.

/// Write \a expr as a string to the output stream \a os, followed
/// by " = " and the \a expr evaluated, followed by '\n'.

#define debug_output( os , expr ) \
  ( ( os ) << #expr << " = " << ( expr ) << '\n' )


namespace cpl {

  
namespace detail_ {

//
// A standard auto_resource_traits class for resource type R.
//

template< typename R >
struct auto_resource_traits ;


//
// A streambuf_traits class must expose two static methods:
//
//   static long read ( R& , char      * const buf , long const n ) ;
//   static long write( R& , char const* const buf , long const n ) ;
//
// Both return either the number of characters read or written or -1
// on error.
//
// n is the number of bytes to be written or read and must be >= 1.
//
// read() tries to read at most n characters.  A return value of zero
// indicates end of file.
//
// write() tries to write n characters.  The return value is either n or
// -1.
//

template< typename R >
struct streambuf_traits ;


} // namespace detail


namespace util {


//
// Assertion failure.  If expr is false, call above die() with the message:
// ``Assertion failed: <expr> (<file>:<line>)''.
//

void assertion(
  const bool expr ,
  std::string const& expr_string ,
  std::string const& file ,
  const long line
) ;

//
// Return current Universal Time Coordinated relative to some fixed
// point [s].  Accuracy is in the order of one second.
//

double const utc() ;


//
// A timer which can be triggered and expires at a fixed time
// afterwards.
//
// Assumes monotonic time.
//

struct triggered_timer {

  // 
  // Set up a switch which will remain on for dt when triggered.
  //
 
  triggered_timer( double const& dt ) 
  : dt( dt )
  { assert( dt > 0 ) ; cancel() ; }

  //
  // Set the timer to untriggered state and start it.  
  // t is the current time.
  //

  void start( double const& t ) { t_trig = t + dt ; }


  //
  // Cancel the timer (set to untriggered state).
  //
  
  void cancel() { t_trig = std::numeric_limits< double >::max() ; }
  
  
  //
  // ``Manually'' trigger the timer (set to triggered state).
  //
  
  void trigger() { t_trig = -std::numeric_limits< double >::max() ; }
  
  
  //
  // Check if timer is triggered.  t is the current time.  Returns true
  // iff more that dt has elapsed since the last start() call or if
  // trigger() has been called.
  //

  bool triggered( double const& t ) const { return t >= t_trig ; }


private:

  double dt     ;
  double t_trig ;

} ;


//
// A simple scheduler for periodic actions requiring approximate timing.
//

struct simple_scheduler {

  //
  // Initialize with given time delta dt.
  //

  simple_scheduler( double const& dt = 0 ) ;

  //
  // Set time delta to dt.
  //
 
  void reconfigure( double const& dt ) ;

  //
  // Return true iff this is the first action() call, t is non-monotonic
  // (less than at the previous action() call) or more than dt has
  // elapsed since last action() call returning true.  The argument t is
  // the current time.
  //

  bool action( double const& t ) ;

private:

  // Time of last action() call returning true.
  double t_last ;

  double dt ;

} ;


// Check if argument is an integer and is in [ min , max ], throw an
// exception if not.

long const check_long
( double const& x , double const& min , double const& max ) ;


/// \return Size of a built-in array (compile-time constant).

template< class T >
inline std::size_t size( T const& a )
{ return sizeof( a ) / sizeof( a[ 0 ] ) ; }


//
// A per-thread death class.
//

struct death {

  death() : os( 0 ) {}

  death( std::ostream* os ) : os( os ) {}

  virtual ~death() { }

  void set_output( std::ostream* os_ ) { os = os_ ; }

  // Exit method may be overridden by the user.
  virtual void exit( int const code ) { std::exit( code ) ; }

  //
  // Try to write \a msg to os,
  // std::cerr, std::clog, \a name in turn.
  // Then call exit() with \a exit_code.  If \a name == "",
  // the system will try to write to "CPP_LIB_DIE_OUTPUT".
  //
  // os is given in the constructor or set by set_output().
  //

  void die(
    std::string const& msg ,
    std::string name = "" ,
    int const exit_code = 1
  ) ;

private:

  std::ostream* os ;

} ;


//
// Some helpers for files.  Implemented in terms of standard C++.
//

namespace file {

//
// owning_istream and owning_ostream are stream classes which
//
// 1. Always have a buffer (DON'T call rdbuf( 0 )).
// 2. Delete their current buffer on destruction.
//

struct owning_istream : std::istream {

  owning_istream( std::auto_ptr< std::streambuf > buf )
  : std::istream( buf.release() )
  { assert( rdbuf() ) ; }

  ~owning_istream()
  { assert( rdbuf() ) ; delete rdbuf() ; }

} ;


struct owning_ostream : std::ostream {

  owning_ostream( std::auto_ptr< std::streambuf > buf )
  : std::ostream( buf.release() )
  { assert( rdbuf() ) ; }

  ~owning_ostream()
  { assert( rdbuf() ) ; delete rdbuf() ; }

} ;


//
// Open a file buffer for reading.
//
// Open the file.  If the operation fails, a std::runtime_error
// containing an appropriate message is thrown.
//
// The function tries all path names path[ i ] + name starting from
// i = 0 and finally tries name alone.
//
// After a successful open, which contains the full pathname of the
// opened file.
//

std::auto_ptr< std::filebuf > open_readbuf(
  std::string const& name  ,
  std::string      & which ,
  std::vector< std::string > const& path = std::vector< std::string >()
) ;


//
// Open a file by delegating to open_readbuf().
//

std::auto_ptr< std::istream > open_read(
  std::string const& name  ,
  std::string      & which ,
  std::vector< std::string > const& path = std::vector< std::string >()
) ;


//
// Equivalent to the above function but without information about
// the opened file.
//

inline std::auto_ptr< std::istream > open_read(
  std::string const& name ,
  std::vector< std::string > const& path = std::vector< std::string >()
) { std::string dummy ; return open_read( name , dummy , path ) ; }


// Open a file buffer for writing.

// Open the file.  If the operation fails, a std::runtime_error
// containing an appropriate message is thrown.

std::auto_ptr< std::filebuf > open_writebuf( std::string const& ) ;


// Open a file for writing by delegating to open_writebuf().

std::auto_ptr< std::ostream > open_write( std::string const& ) ;


// Strip suffix from filename.

// If name ends in suffix, return name with suffix removed.
// Otherwise, return name.

std::string basename( std::string const& name , std::string const& suffix ) ;


// A class to redirect an ostream to a file.

struct redirector {

  //
  // As long as the redirector exists, os is redirected to file name
  // by switching the buffer.
  //

  redirector( std::ostream& os , std::string const& name ) :
    file( cpl::util::file::open_write( name ) ) ,
    saved( os.rdbuf() ) ,
    redirected( os )
  { os.rdbuf( file->rdbuf() ) ; }

  /// Restore the original buffer.

  ~redirector() {
    always_assert( saved != 0 ) ;
    redirected.rdbuf( saved ) ;
  }

private:

  /// The file to redirect to.

  std::auto_ptr< std::ostream > file ;

  /// The saved stream buffer.

  std::streambuf* saved ;

  /// The redirected stream.

  std::ostream& redirected ;

} ;


} // namespace file


//
// Set stream where die() should write its message.  \a os must
// point to a valid open ostream or be zero.
//

void set_die_output( std::ostream* os ) ;

//
// Construct a death object with the ostream given in set_die_output()
// and call its die() method with the given parameters.  Backward
// compatibility function, use of death class is preferred.
//

void die(
  std::string const& msg ,
  std::string name = "" ,
  int const exit_code = 1
) ;


//
// Toggle a boolean.
//

inline void toggle( bool& b ) { b = !b ; }


/// Lexical cast of arbitrary type to std::string.

template< typename T >
std::string string_cast( T const& ) ;

//
// Chop whitespace at the end of a string.
//

void chop( std::string& ) ;


//
// Read characters from is until either is goes bad or the given
// character sequence string is encountered.
//

void scan_past( std::istream& is , char const* const string ) ;


//
// Converts an integer into a std::vector< char >.
//
// The most significant byte is put into the first element in the vector!
// The vector's size will be the same as type T's in byte.
//
// Author:  Marco Leuenberger.
//

template< typename T >
std::vector< char > to_char_vector( T const& ) ;


//
// Converts a std::vector< char > into an integer.
//
// The most significant byte must be the first element in the vector!
// The vector's size must be the same as type T's in byte!
//
// Author:  Marco Leuenberger.
//

template< typename T >
T to_integer( std::vector< char > const& ) ;


//
// Convert a (time) value t >= 0 into its integral part s and fractional
// part f, 0 <= f < m such that
//
//   t approximately equals s + f/m.
//
// S and F should be integral types.
//

template< typename S , typename F >
void to_fractional( double const& t , long const m , S& s , F& f ) {

  assert( m > 0 ) ;

  always_assert( t >= 0 ) ;

  // Round.
  double const tt = std::floor( t * m + .5 ) / m ;

  always_assert( tt >= 0 ) ;

  double const i = std::floor( tt ) ;

  s = static_cast< S >( i ) ;

  double const ff = m * ( tt - i ) ;
  always_assert( 0 <= ff       ) ;
  always_assert(      ff < m ) ;

  f = static_cast< F >( ff + .5 ) ;
  always_assert( 0 <= f     ) ;
  always_assert(      f < m ) ;

}


//
// A dirty hack to clear out an arbitrary structure.
//

template< typename T >
void clear( T& t ) {

  char* adr = reinterpret_cast< char* >( &t ) ;

  std::fill( adr , adr + sizeof( T ) , 0 ) ;

}


//
// Unidirectional stream buffers based on streambuf_traits<>.
//
// This implementation is based on code by Nico Josuttis which was 
// accompanied by the following notice:
/*
 *
 * (C) Copyright Nicolai M. Josuttis 2001.
 * Permission to copy, use, modify, sell and distribute this software
 * is granted provided this copyright notice appears in all copies.
 * This software is provided "as is" without express or implied
 * warranty, and with no claim as to its suitability for any purpose.
 *
 */

// 
// For implementation of streambufs, see also the newsgroup postings of
// Dietmar Kuehl, in particular:
//   http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&oe=UTF-8&selm=5b15f8fd.0309250235.3200cd43%40posting.google.com
//
// and
//
//   Josuttis, The C++ Standard Library, Chapter 13 (p. 678)
//
// The relevant standard chapter: 25.1.
//
// See also the crypt_istreambuf implementation.
//
// TODO: Implement xsputn().
//

// From Nico's original comment:
/*
 * - open:
 *      - integrating BUFSIZ on some systems?
 *      - optimized reading of multiple characters
 *      - stream for reading AND writing
 *      - i18n
 */

template
< typename R , typename T = cpl::detail_::streambuf_traits< R > >
struct ostreambuf : virtual std::streambuf {

  //
  // Construct an ostreambuf on resource r with buffer size.
  //

  ostreambuf( R& r , int const size = 1024 )
  : r     ( r    ) ,
    buffer( size )
  { 
    
    always_assert( size >= 1 ) ; 
    setp( &buffer[ 0 ] , &buffer[ 0 ] + size - 1 ) ; 
  
  }

  virtual ~ostreambuf() { sync() ; T::shutdown_write( r ) ; }

protected:

  //
  // See 27.5.2.4.5p3
  // Failure: EOF, success: != EOF.
  //

  virtual int_type overflow( int_type c ) {

    if( traits_type::eof() != c ) {

      *pptr() = traits_type::to_char_type( c ) ;
      pbump( 1 ) ;

    }

    return flush() ? c : traits_type::eof() ;

  }

  //
  // See 27.5.2.4.2p7. ``Returns -1 on failure''.
  //

  virtual int sync() { return flush() ? 0 : -1 ; }


private:

  //
  // Like sync(), but return a bool (true on success).
  //

  bool const flush() ;

  R& r ; 
  
  std::vector< char > buffer ;

} ;


template
< typename R , typename T = cpl::detail_::streambuf_traits< R > >
struct istreambuf : virtual std::streambuf {
  
  //
  // Construct an istreambuf on resource r buffer
  // size size and putback area size size_pb.
  //

  istreambuf( 
    R&        r              , 
    int const size    = 1024 ,
    int const size_pb = 4 
  ) 
  : r( r ) ,
    size_pb( size_pb ) ,
    buffer( size + size_pb , 0 ) {

    always_assert( size    >= 1 ) ;
    always_assert( size_pb >= 1 ) ;
   
    char* const p = &buffer[ 0 ] + size_pb ; 
    setg( p , p , p ) ;

  }
  
  virtual ~istreambuf() { T::shutdown_read( r ) ; }

protected:

  virtual int_type underflow() ;

private:

  R& r ;

  // Size of putback area.
  int const size_pb ; 

  std::vector< char > buffer ;

} ;


//
// A resource manager template with semantics similar to
// std::auto_ptr<>.  Needs a traits class T with static methods
//
//   R const T::invalid()                     -- Return an ``invalid'' resource 
//                                               handle.
//   bool    T::valid( R const& h )           -- Return true iff h is valid. 
//   void    T::dispose( R const& h ) throw() -- Return h to the OS.
//

template
< typename R , typename T = cpl::detail_::auto_resource_traits< R > >
struct auto_resource {

  auto_resource(                    ) : h( T::invalid()  ) {}
  auto_resource( R const& h         ) : h( h             ) {}
  auto_resource( auto_resource& rhs ) : h( rhs.release() ) {}

  auto_resource const& operator=( auto_resource& rhs ) 
  { reset( rhs.release() ) ; return *this ; }

  R const& get() const { return h ; }

  R const release() 
  { R const ret = h ; h = T::invalid() ; return ret ; }

  bool valid() const { return T::valid( h ) ; }

  void reset( R const& hh = T::invalid() ) { dispose() ; h = hh ; }

  ~auto_resource() { dispose() ; }

private:

  void dispose() const { if( T::valid( h ) ) { T::dispose( h ) ; } }

  R h ;

} ;


} // namespace util

} // namespace cpl


//
// Template definitions.
//

template< typename R , typename T >
bool const cpl::util::ostreambuf< R , T >::flush() {

  long const n = pptr() - pbase() ;

  assert( 0 <= n                                         ) ;
  assert(      n <= static_cast< long >( buffer.size() ) ) ;

  if( 0 == n ) { return true ; }

  long const written = T::write( r , pbase() , n ) ;

  if( written < 0 ) { return false ; }

  assert( n == written ) ;

  pbump( -n ) ;
  assert( pptr() == &buffer[ 0 ] ) ; 
  return true ;

}


template< typename R , typename T >
typename cpl::util::istreambuf< R , T >::int_type
cpl::util::istreambuf< R , T >::underflow() {

  if( gptr() < egptr() ) 
  { return traits_type::to_int_type( *gptr() ) ; }

  int const n_pb = 
    std::min( 
      static_cast< long >( gptr() - eback() ) , 
      static_cast< long >( size_pb          ) 
    ) ;

  std::memmove( &buffer[ 0 ] + size_pb - n_pb , gptr() - n_pb , n_pb ) ;

  long const read = 
    T::read( r , &buffer[ 0 ] + size_pb , buffer.size() - size_pb ) ;
  
  if( read <= 0 ) { return traits_type::eof() ; }

  setg(
    &buffer[ 0 ] + size_pb - n_pb , // beginning of putback area
    &buffer[ 0 ] + size_pb        , // read position
    &buffer[ 0 ] + size_pb + read   // end of buffer
  ) ;

  return traits_type::to_int_type( *gptr() ) ;

}

//
// Template definitions.
//

template< typename T >
std::string cpl::util::string_cast( T const& x ) {

  std::ostringstream os ;
  os << x ;
  return os.str() ;

}


template< typename T >
std::vector< char > cpl::util::to_char_vector( T const& x ) {

  assert( std::numeric_limits< T >::is_integer );

  std::vector< char > vec;
  unsigned int size;

  if( std::numeric_limits< T >::is_signed )
  {
    size = ( std::numeric_limits< T >::digits + 1 ) / 8 ;
  }
  else
  {
    size = std::numeric_limits< T >::digits / 8 ;
  }
     
  for( unsigned int i = size ; i > 0 ; --i )
  {
    vec.push_back( static_cast< char >( ( x >> ( ( i-1 ) * 8 ) ) & 0xFF ) );      
  }
  
  return vec ;

}


template< typename T >
T cpl::util::to_integer( std::vector< char > const& vec ) {

  assert( vec.size() == sizeof( T ) );

  T x = static_cast< T >( static_cast< unsigned char > ( vec[0] ) );
  
  for( unsigned int i = 1 ; i < vec.size() ; ++i )
  {
    x <<= 8;
    x = x + static_cast< T >( static_cast< unsigned char > ( vec[i] ) );
  }
  
  return x ;

}

#endif // CPP_LIB_UTIL_H
